#include "searchInsert.h"

int searchInsert(std::vector<int>& nums, int target)
{
	int numsLength = nums.size();
	if (numsLength == 0)
	{
		return 0;
	}

	if (numsLength == 1)
	{
		if (nums.at(0) < target)
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}

	bool isWhile = true;
	int left = 0;
	int right = numsLength - 1;
	int mid = (left + right) / 2;
	while (isWhile)
	{
		if (left == mid || right == mid)
		{
			if (target > nums.at(left) && target > nums.at(right))
			{
				return right + 1;
			}
			else if (target > nums.at(left) && target < nums.at(right))
			{
				return left + 1;
			}
			else if (nums.at(left) == target)
			{
				return left;
			}
			else if (nums.at(right) == target)
			{
				return right;
			}
			else if (target < nums.at(left) && target < nums.at(right))
			{
				return (left - 1) > 0 ? (left - 1) : 0;
			}
		}

		if (nums.at(mid) == target)
		{
			return mid;
		}
		else if (nums.at(mid) < target)
		{
			left = mid;
		}
		else
		{
			right = mid;
		}

		mid = (left + right) / 2;
		
	}
	return 0;
}
